\documentclass{bsys}

\begin{document}

% \maketitle{Nummer}{Abgabedatum}{Tutor-Name}{Gruppennummer}
%           {Teilnehmer 1}{Teilnehmer 2}{Teilnehmer 3}
\maketitle{1}{27.11.2007}{Kirsten}{7}
          {Eric Gomdjim Kuitche}{Tchando Kongue}{Tchambo Frantz}{Mba Nouga}

\section{Mutual Exclusion N = 2}
\begin{itemize}
\item[a)]\textbf{Erl"auterung der Funktionsweise des Algorithmus} \\ \\ 
Das Algorithmus dient zur Verwaltung der Kritische Region, die von zwei Parallel Prozesse eingetreten wird. Das Ziel dieses Algorithmus ist zu vermeidern, dass  zwei Prozesse gleichzeitig die Kritische Region eintreten.

 \item In \textbf{turn} wird der Pid des Prozess, das am letzten die kritische Region eintreten m"ochte, gespeichert.
 
 \item blocked ist ein Array von zwei Boolean. Der Wert von jede Zelle entspricht, das Interest des koresporendierten Prozesses f"ur die kritische Region.\\
 Anfangzustand: turn ist mit 0 initialisiert und blocked von  vorhandene Prozesse mit false
\begin{center}
\textbf{Ablauf des Algorithmus}
\end{center}
 Das eintreten und das Velassen der kritische Region werden jeweils mittel die Methode enter\_region und leave\_region verwalten.\\
Wenn ein Prozess x aus \{0,1\} in kritische Region will, wird die Methode enter\_region aufgerufen\\
\item Sein pid wird gelesen
\item  Sein Interest(blocked[x]) wird auf true gesetzt 
\item nun wird "uberpr"uft ob sein pid gleich turn ist. Es unterscheidet sich zwei F"alle\\ \\
Fall 1:\textbf{ turn == pid} \\ 
In diesem Fall kann das Prozess sofort die kritische Region eintreten und danach wird die Methode leave\_region aufgerufen, die das Interest des Prozess x ( blocked[x]) wieder auf false zur"uck setzt.\\ \\

Fall 2: \textbf{turn != pid}\\ 
In diesem Fall wird noch gepr"uft, ob das andere Prozess f"ur die kritische Region interessiert ist.\\
Falls ja bleibt das Prozess in der While schleife h"angen, bis Interest von anderem Prozess
wieder false wird.\\
Falls nein schreibt sein pid in der globale Variable turn und springt wieder bei Fall2.\\
\item[b)] CSP-Spezifikation des Algorithmus


\begin{listingcont}
-- Allgemeiner Ablauf
PROCESS(pid) = ENTER(pid);  		---enter_region
               enter_critical!pid ->  
	       leave_critical!pid ->
	       LEAVE(pid);  		---leave_region
	       PROCESS(pid)

----------enter_region
ENTER(pid) = write_blocked.pid!true -> ---zuweisen true an blocked[pid]
	     WHILE1(pid);             ---- erste while schleife
             SKIP

----------erste while schleife
WHILE1(pid) = read_turn?x ->     ----turn auslesen
             if(x !=pid) then    ----x turn mit pid vergleichen
	       WHILE2(pid);      ---- zweite while schleife starten
		write_turn!pid-> ---- turn mit pid zuweisen
		WHILE1(pid)	 ---- erste while schleife weitermachen
             else
               SKIP		 ---- wenn pid!=turn, stop die erste while schleife

---------- zweite while schleife
WHILE2(pid) = read_blocked.(1-pid)?x ->  --- blocked[1-pid] auslesen
             if(x) then			 --- wenn true, dann muss warten
	       WHILE2(pid)		 --- warten: schleife weitermachen
             else
               SKIP			 --- sonst musst nicht warten
 
----------Leave_region
LEAVE(pid) = write_blocked.pid!false ->  --- blocked[pid] = false
             SKIP
\end{listingcont}

\item[c)] Verifikation des Algorithmus "uber einem Watchdog und einer Trace Refinement.\\

Da das Algorithmus wie das Peterson's Algorithmus funktionnieren musst, wird es keine grosse "Anderung an der Implementierung von der Watchdob und Trace Refinement aus der Vorlesung-Ubung gemacht.

Die Verifikation "uber einem Watchdog  f"uhrt zu einem Deadlock, das gesamt System wird angehaltet (Es wird nicht terminiert). Der Watchdog merkt, dass eine nicht erlaubte Folge von Event(\verb# enter_critical.1, enter_critical.0# ) ausgef"uhrt wird. Also die beiden Prozesses k"onnen gleichzeigtig das krittische Abschnitt betretten.

Die Kontrolle mit Trace Refinement \verb# assert ASYS [T= SYSTEM # findet der gleiche Fehler. Es merkt dass alle m"oglichen Traces von\verb# SYSTEM# nicht in der Abstract System\verb# ASYS# enhaltet sind.

Das Algorithmus kann nicht gew"ahrleisten, dass immer nur ein Prozess in der Kritischen Abschnitt landet. Der Grund ist die nicht gute(zeitliche gesehen) Initialisierung des Array \verb#blocked#. Das Fehler kann sich ab der zweite ``while'' schleife merken lassen: Wenn der zweite Prozess(mit id 1) blocked[1-pid] ausliest, k"onnte es sein das diese noch nicht initialisiert ist. Das heisst, der kann jetzt zu der Zuweissungsschrit von turn springen. Aber bevor die Zuweisung gemacht wird, kann jetzt der erste Prozess(mit id 0) starten, der erste Prozess kann dann in kritische Abschnitt springen bevor die Variable turn initialisiert wird. Nach dem Sprung von dem erste Prozess, der Prozess mit pid=1 initialisiert turn mit seinem PID und geht auch in kritische Abschnitt.

\begin{tabular}{|l|l|}
\hline
Prozess 0		& Prozess 1\\\hline
  			& blocked[1] = true\\
   			&	turn auslesen : \bf{0} \\
 			&	 blocked[0] auslesen :\bf{false} \\
blocked[0] = true 	& \\
turn auslesen: \bf{0} 	& \\
enter\_critical0 	& \\
			& turn = 1 \\
			& turn aulesen : \bf{1} \\
			& enter\_critical1\\\hline
\end{tabular}

\item[d)] Ver"anderung des Algorithmus\\
Damit der Peterson's Algorithmus entspricht wird, kann man an den Algorithmus die 3 folgende "Anderungen machen:

\begin{itemize}
\item[*]Die Variable ``turn'' zuweisen, vor der beide Schleife, mit dem Wert $(1-pid)$(zeile 40). 
\item[*]Die erste Schleife ruft sich nicht mehr(Zeile 47).
\item[*]Die letzte Schleife ruft die erste Schleife statt sich selbst(Zeile 53).
\end{itemize} 
 
\begin{listingcont}-- Allgemeiner Ablauf
PROCESS(pid) = ENTER(pid); 
               enter_critical!pid -> 
	       leave_critical!pid ->
	       LEAVE(pid);
	       PROCESS(pid)

ENTER(pid) = write_blocked.pid!true ->
	     write_turn!(1-pid)-> // turn initialisiert mit (1-pid)
	     WHILE1(pid);
             SKIP

WHILE1(pid) = read_turn?x ->
             if(x !=pid) then
	       WHILE2(pid) // Zeile write_turn!pid verschwinden
			   // WHILE1 verschwindet 
             else
               SKIP

WHILE2(pid) = read_blocked.(1-pid)?x ->
             if(x) then
	       WHILE1(pid) // WHILE1 statt WHILE2
             else
               SKIP
 
LEAVE(pid) = write_blocked.pid!false ->
             SKIP

\end{listingcont}
Die erste "Anderung bewirkt dass, die Variable turn am Anfang initialisiert wird. Aus die zweite und dritte "Anderung, wird die beide \textit{while} als eine \textit{while-if} transformieren. Diese dreie "Anderungen bewirken, dass das Ablauf die gleiche Ergebniss wie der Peterson's Algorithm ergibt.

Aus der transformierte CSP Algorithmus, entsteht der folgende c-code. Der ist equivalent zu Petersons Code.

\begin{listingcont}
 void enter_region(int pid)
{
	blocked[pid] = true;
	turn 	     = 1-pid;
	while(turn!=pid)
		if(blocked[1-pid]);
		break;
}

void leave_region(int pid)
{
	blocked[pid] = false;
}
\end{listingcont}


\end{itemize}
\section{Mutual Exclusion N $\geq$ 2}

\begin{listing}{1}
 #define N                          //number of processes
int x;                             //in {1..N}
int y;                             //in {0..N}, initialized with 0
bool blocked[N+1]                  //initialized with false
void enter_region(int pid)
{
  int j;
  start: blocked[pid] = true;
         x = pid;
         if(y != 0)
         {
           blocked[pid] = false;
           while(y != 0)
             ;                     //active wait
           goto start;
         }
         y = pid;
         if(x != pid)
         {
           blocked[pid] = false;
           for(j = 1; j <= N; j++)
             while(blocked[j])
               ;                   //active wait
           if(y != pid)
           {
             while(y != 0)
               ;                   //active wait
             goto start;
           }
         }
}
void leave_region(int pid)
{
  y = 0;
  blocked[pid] = false;
}

\end{listing}

\begin{itemize}
\item[a)] Das Algorithmus dient zur Verwaltung einer kritische Region ,die von N Prozesse eingetreten wird. Das Ziel ist wie oben zu verhindern,dass mehr als ein prozess gleichzeitig  in die kritische Region eintreten.
Die globale variable x und y von Typ Integer werden als Hilfsvariable ben"otigt, um die PID von Prozesse zu speichern, und wieder zu lhern.Das Array-blocked nimmt die  Werte \textbf{true} oder \textbf{false}: bockled[x]= true heisst, dass das Prozess mit der pid x fr die kritische abschnitt interessiert ist.\\
\begin{center}
\textbf{Ablauf des Algorithmus}
\end{center}
\item[ ]Wenn ein prozess \textbf{k} f"ur die kritische Region interessiert ist, wird seinen PID gelesen, \textbf{true} wird sein blocked zugewiesen und sein pid wird in der variable x geschrieben. Es wird dann "uberprft, ob kein andere Prozess die variable y (zeile 17) ge"andert hat und die Methode  \textbf{leave\_region} noch nicht aufgerufen hat. Es unterscheidet sich zwei F"alle.\\
\textbf{Fall 1 : y==0 (Zeile 10) d.h. es gibt kein Prozess der schon vor Prozess k  die Variable y (Zeile 17) ge"andert hat}\\
In diesem Fall muss Prozess k nicht warten und schreibt sofort sein  PID   in der Variable \textbf{y (zeile 17)} .\\
 \textbf{Fall 2 : y != 0 (Zeile 10) }
In diesem Fall wird sein Interest abgelehnt (\textbf{blocked[k]=false})und h"angt k in der While-schleife (Zeile 13) bis die kritische region wieder frei wird. Wenn die kitische Region frei wird, f"angt Prozess k wieder von Vorn(Zeile 8) an.\\
\item[] Nachdem ein Prozess die  Variable y (Zeile 17) ge"andert hat, wird "uberpr"uft,ob ein anderes Prozess interesse gezeigt hat und sein PID in de Variable x (Zeile 9) geschrieben hat.\\ 
\textbf{Falls Ja: } wird das Interess des Prozess k auf false gesetzt(Zeile 20)  und bleibt Prozess k in der for-Schleife (Zeile 21) h"angen bis das Interesse von alle andere laufende Prozesse wieder false wird. Nun wird "uberpr"uft, ob den Aktuellen Wert von y das PID von Prozess k ist d.h \textbf{(*)} ein prozess hat gerade die kritische Region verlassen oder \textbf{(**)} ein Prozess hat die Variable y (Zeile 17) ge"andert.\\
\textbf{(*)} begin Prozess k wieder von Vorn(Zeile 8)\\
\textbf{(**)} Falls kein Prozess die Kritische region verlassen hat dh (y!=pid \&\& y!=0),bleibt Prozess k in der  while-Schleife(Zeile 26) h"angen und wartet bis ein Prozess die kritische Region verl"ast. \\ 
\textbf{Falls Nein :} kommt das Prozess sofort in der kritische Region und  verl"ast danach die kritische Region wobei 0 die Variable y zugewiesen wird und blocked[k] auf false gesetzt wird.

\item[b)] Das Algorithmus scht"uzt vor \textbf{Deadlocks}: Kein Prozess kann warten ohne etwas zu tun, alle ``wait'' sind actif, da das Programcounter sich immer mindesten in einer endlos leeren schleife bewegen kann, das Mutex Mechanimus fordert kein ``Sleep''.  Der sch"utzt auch vor \textbf{livelocks}, weil h"ochsten \textbf{N-1} Prozesse blockiert werden k"onnen d.h wenn mehrere Prozesse ihre Interesse zeigen, kann nur das Prozess, das zuletzt seinen pid in der Variable x \textbf{Zeile 9} geschrieben hat, die if-Anweisung (Zeile 18) springen und alle andere interessierte Prozesse blockieren. Wegen der Splitter (frage c) kann alle Prozesse nicht gleichzeitig in der Methode \textit{enter\_region} unendlich rumlaufen.

Das Algorithmus kann aber nicht vor \textbf{Starvation} sch"utzen. Wenn ein Prozess schon seinen \textbf{pid} in der variable \textbf{y }(Zeile 17)geschrieben hat, dann bleiben alle weitere Prozesse, die danach ihre Interessse zeigen, in der while-schleife(\textbf{Zeile 13} ) h"angen und warten auf das Ereignis \textbf{y == 0}. Wenn das Ereignis endlich auftaucht,fangen wieder alle prozesse von vorn(\textbf{zeile 8}) an und haben wieder die gleiche Chance. Es kann also passieren, dass ein (oder mehrere)  Prozess(e) niemals die kritische Region eintreten, obwohl sie immer wierder ihre Interesse zeigen. Also die zufall Auswahl des Prozess der in kritische Abschnitt sollt kann starvation verursachen(im Gegenteil von Peterson, bei dem fast immer der am l"angsten wartende Prozess in kritische Abschnitt musst).


\item[c)] Geschwindigkeit\\
Peterson  : Jeder Prozess bevor, der in kritische landet, musst mindesten die ganze beide ``for'' schleife durchlaufen (complexit"at $>= O(n^2)$). Das Algorithmus sortiert die Prozesse (Das Prozess der mehr gewartet hat, musst zuerst in kritische Abschnitt). Die Sortierung verlangsam jeder Prozess vor der kritische Abschnitt (im vergleich zu diesem Algorithmus).

Mit diesem Algorithmus kann ein Prozess mit einem Complexit"at von O(1) direkt in kritischen Abschnitt gehen(Einfach die beiden ``if'' "uberqueren). Die Prozesse werden nicht sortieren (es gibt keine determistisch verschalte schleife), wenn der kritische Abschnitt freie ist, haben generell alle wartende Prozess direckte die gleiche chance f"ur das kritische Abschnitt. Dieses Eingenschaft beschleunigt das verfahren zu vergleich zu peterson's Algorithmus.

\item[d)] Splitter\\
Zwischen alle Prozessen, die in kritischen Abschnitten wollen, wird das Codesegment nur ein dem krittischen Abschnitt beitreten lassen und die andere warten lassen. Also das Codesegment w"ahlt ein Prozess aus der Menge von interessierten Prozesse, deshalb wird er als Splitter bezeichnet.

Nur ein Prozess kann an die beiden ``if'' (in einem Durchlauf) mit ``nein'' antworten. Bei dem ersten ``if'' wartet der Prozess, wenn die Variable y schon initialisiert ist (das Prozess mit pid = y darf schon fast/oder ist schon  in kritische Abschnitt).

 Ein Prozess erreicht der zweite ``if'', wenn der kritische Abschnitt freie ist. Der letzte Prozess, der die Variable \textit{x} initialisiert hat (x!=pid), darf direkt in kritische Abschnitt. Die andere warten.

\end{itemize}
\end{document}

